package com.itheima.leetcode.od.b.dynamicprogramming;

/**
 * (B卷,100分)- 数列描述（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 有一个数列a[N] (N=60)，从a[0]开始，每一项都是一个数字。数列中a[n+1]都是a[n]的描述。其中a[0]=1。规则如下：
 * <p>
 * a[0]:1
 * a[1]:11(含义：其前一项a[0]=1是1个1，即“11”。表示a[0]从左到右，连续出现了1次“1”）
 * a[2]:21(含义：其前一项a[1]=11，从左到右：是由两个1组成，即“21”。表示a[1]从左到右，连续出现了两次“1”)
 * a[3]:1211(含义：其前一项a[2]=21，从左到右：是由一个2和一个1组成，即“1211”。表示a[2]从左到右，连续出现了1次“2”，然后又连续出现了1次“1”)
 * a[4]:111221(含义：其前一项a[3]=1211，从左到右：是由一个1、一个2、两个1组成，即“111221”。表示a[3]从左到右，连续出现了1次“1”，连续出现了1次“2”，连续出现了两次“1”)
 * 请输出这个数列的第n项结果（a[n]，0≤n≤59）。
 * <p>
 * 输入描述
 * <p>
 * 数列的第n项(0≤n≤59)
 * <p>
 * 4
 * <p>
 * 输出描述
 * <p>
 * 数列的内容
 * <p>
 * 111221
 * <p>
 * 用例
 * <p>
 * 输入	4
 * 输出	111221
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 这题是一个典型的动态规划题目，因为它存在明显的：下一个阶段状态依赖于上一个阶段状态，存在状态转移。
 * <p>
 * 这题难点在于找状态转移方程，即上一个状态与上一个状态之间的变化关系，按照题目意思应该是一种描述关系。即下一个状态是对于上一个状态的描述。
 * <p>
 * 我这边实现：比如上一个状态是1211，则将其转为字符数组arr，取出第0个字符缓存到变量val中，并定义一个变量count，用于记录val字符出现的次数。
 * <p>
 * 然后开始遍历字符数组，从第1个开始遍历，比较arr[0]和arr[1]，如果相同，则count++，如果不同，则输出描述count + "" + val，然后将arr[1]作为新的val，并且count重置为1，接着比较arr[1]和arr[2]，逻辑如上。
 */
public class SequenceDescription {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();*/

        int n = 4;

        System.out.println(getSeq(n));
    }

    public static String getSeq(int n) {
        String base = "1";
        for (int i = 1; i <= n; i++) {
            base = describe(base);
        }
        return base;
    }

    public static String describe(String seq) {
        StringBuilder sb = new StringBuilder();

        int count = 1;
        char val = seq.charAt(0);

        for (int i = 1; i < seq.length(); i++) {
            if (seq.charAt(i) == seq.charAt(i - 1)) {
                count++;
            } else {
                sb.append(count).append(val);
                count = 1;
                val = seq.charAt(i);
            }
        }
        sb.append(count).append(val); // 记得添加最后一次的 count val
        return sb.toString();
    }
}